A data word has to be processed in a variety of applications in a plurality of cycles, for example in a block correlation. A block correlation can be employed for determining the phase shift between a known data word and a received data word, for instance for tracking satellite signals in a satellite based navigation system.
In the Global Positioning System (GPS), for example, code modulated signals are transmitted by several satellites that orbit the earth and received by GPS receivers of which the current position is to be determined. Each of the satellites transmits two microwave carrier signals. One of these carrier signals L1 is employed for carrying a navigation message and code signals of a standard positioning service (SPS). The L1 carrier signal is modulated by each satellite with a different C/A (Coarse Acquisition) code known at the receivers. Thus, different channels are obtained for the transmission by the different satellites. The C/A code, which comprises values of −1 and 1 and which is spreading the spectrum over a 1 MHz bandwidth, is repeated every 1023 chips, the epoch of the code being 1 ms. The term chips is used to designate the bits of the C/A code. The carrier frequency of the L1 signal is further modulated with the navigation information at a bit rate of 50 bit/s. The navigation information, which constitutes a data sequence, can be evaluated for example for determining the position of the respective receiver.
A receiver receiving a code modulated signal has to have access to a synchronized replica of the employed modulation code, in order to be able to de-spread the data sequence of the signal. More specifically, a synchronization has to be performed between the received code modulated signal and an available replica code. Usually, an initial synchronization called acquisition is followed by a fine synchronization called tracking. In both synchronization scenarios, correlators are used to find the best match between the replica code sequence and the received signal and thus to find their relative shift called code phase. During the acquisition, the phase of the received signal relative to the available replica code can have any possible value due to uncertainties in the position of the satellite and the time of transmission of the received signal.
As correlators, for instance block correlators can be employed.
FIG. 1 is a diagram which schematically illustrates the operation of a block correlator.
The correlator has access to a known fixed data word, for instance a C/A code. In the presented example, this data word is represented by the bit sequence ‘ABCDEFGHI’. Further, samples are input to the correlator, for instance samples of a received satellite signals. In the presented example, these samples are represented by the bit sequence ‘abcdefghiabc . . . ’. Now, the correlator is to determine the correlation between the available data word and the input samples for each possible phase shift between the available data word and the received samples.
The block correlator divides to this end the entire available data word continuously into N=3 data blocks, each having a length of L=3 samples, namely block ‘ABC’, block ‘DEF’ and block ‘GHI’. This is indicated in section 11 of FIG. 1. The first L=3 incoming samples ‘abc’ are indicated in section 12 of FIG. 1.
The correlator then multiplies the bits of each block with the first L=3 incoming samples ‘abc’, integrates the respective multiplication results, and stores the respective integration result in a memory at successive memory addresses. For example, the value ‘A*a+B*b+C*c’ is stored at memory address ‘1’, the value ‘D*a+E*b+F*c’ is stored at memory address ‘2’ and the value ‘G*a+H*b+I*c’ is stored at memory address ‘3’. Each of the stored integration result represents a partial correlation value.
The same procedure is repeated for input samples ‘bcd’, the integration results being stored at successive memory addresses ‘4’, ‘5’ and ‘6’, respectively. The same procedure is further repeated for input samples ‘cde’, the integration results being stored at successive memory addresses ‘7’, ‘8’ and ‘9’.
Now, the first three input samples ‘abc’ are processed completely, and all N×L employed memory addresses ‘1’ to ‘9’ are filled with partial correlation results for a particular phase shift. This memory allocation is indicated on the left hand side of section 13 of FIG. 1.
The block correlator continues dividing the entire available data word into N=3 data blocks ‘ABC’, ‘DEF’ and ‘GHI’. The described multiplications and integrations are repeated for each of the next N×L data blocks and the next three input samples ‘def’. The integration results, which are indicated on the right hand side of section 13 of FIG. 1, are added at appropriate memory addresses to the already stored partial correlation values, as indicated by arrows in section 13 of FIG. 1.
For example, the value ‘A*d+B*e+C*f’ is added to the current value stored at memory address ‘3’, the value ‘D*d+E*e+F*f’ is added to the current value stored at memory address ‘1’ and the value ‘G*d+H*e+I*f’ is added to the current value stored at memory address ‘2’, etc.
When the input samples ‘def’, have been processed completely, the block correlator still continues dividing the entire available data word into N=3 data blocks ‘ABC’, ‘DEF’ and ‘GHI’. The described multiplications and integrations are repeated for each of the next N×L data blocks and the last three input samples ‘ghi’. The integration results are added at appropriate memory addresses ‘1’to ‘9’ to the already stored partial correlation values to obtain final correlation values for each phase shift. This processing part is not shown anymore in FIG. 1.
Thus, the final correlation value stored at memory address ‘1’ is ‘A*a+B*b+C*c+D*d+E*e+F*f+G*g+H*h+I*i’, the final correlation value stored at memory address ‘2’ is ‘D*a+E*b+F*c+G*d+H*e+I*f+A*g+B*h+C*i’, the final correlation value stored at memory address ‘3’ is ‘G*a+H*b+I*c+A*d+B*e+C*f+D*g+E*h+F*i’, etc. On the whole, there are nine different correlation values for nine different phase shifts between the available code and the incoming samples stored at memory addresses ‘1’ to ‘9’.
As can be seen in FIG. 1, the combination of new partial correlation values with stored partial correlation values requires jumps between memory addresses when accessing the memory. Therefore, the memory address has to be calculated for each combination by a complex state machine.
In particular in case much more than nine samples belong to a data word, the computational effort by means of a state machine is considerable. For GPS receivers, for instance, it is known to use N=31 blocks with L=66 samples each for a single repetition of a C/A code.